/**
 * https://leetcode.cn/submissions/detail/583980999/
 * 1926. 迷宫中离入口最近的出口
 * Medium, 黄伟杰 2024.11.29
 * BFS
 */

class Solution
{
    int ds[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 上下左右移动
public:
    int nearestExit(vector<vector<char>> &maze, vector<int> &entrance)
    {
        int n = maze.size();                     // 行
        int m = maze[0].size();                  // 列
        maze[entrance[0]][entrance[1]] = '+';    // 将起点设置为墙
        int sta = entrance[0] * m + entrance[1]; // 给起点编号
        queue<pair<int, int>> q;
        q.emplace(sta, 0); // 存入id和步数
        while (!q.empty())
        {
            auto p = q.front();
            int i = q.size();
            q.pop();
            int r = p.first / m, c = p.first % m,
                v = p.second; // 这个结点的（r，c）
            for (; i > 0; i--)
            {
                for (auto &d : ds)
                {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr == -1 || nr == n || nc == -1 || nc == m ||
                        maze[nr][nc] == '+')
                        continue;
                    if (nr == 0 || nr == n - 1 || nc == 0 || nc == m - 1)
                        return v + 1;
                    int np = nr * m + nc;
                    q.emplace(np, v + 1);
                    maze[nr][nc] = '+';
                }
            }
        }
        return -1;
    }
};